# !/usr/bin/python
# -*- coding: utf-8 -*-
"""
@version: V1.0
@author: Coffen
@file: yimeta_b1_reply
@time: 2025/2/18 08:00
"""

import copy
import random


class Q1StudentCode:
    """
    第一题：实现一个类， 用来存储一个班级的学号 。实现以下方法：
    1. 添加一个学号
    2. 查找一个学号是否存在（时间复杂度要求： O(1)）
    3. 删除一个学号
    4. 随机返回一个学号
    5. 返回一个最小的学号（时间复杂度要求： O(1)）
    """

    def __init__(self, lst_stu=None):
        """
        初始化班级列表
        :param lst_stu: 学号列表
        """
        self.students = set(lst_stu) if lst_stu and isinstance(lst_stu, (list, set)) else ()

    def add(self, stu_code):
        """
        添加一个学号
        :param stu_code: 学号
        :return:
        """
        if not self.exists(stu_code):
            self.students.add(stu_code)

    def exists(self, stu_code):
        """
        判断学号是否存在
        :param stu_code:
        :return: True/False
        """
        return stu_code in self.students

    def remove(self, stu_code):
        """
        删除一个学号
        :param stu_code:
        :return: 删除成功与否 True/False
        """
        if self.exists(stu_code):
            self.students.remove(stu_code)
            return True
        return False

    def get_random(self):
        """
        随机一个学号
        :return: stu_code
        """
        return random.choice(list(self.students)) if self.students else None

    def get_min(self):
        """
        获取最小学号
        :return: stu_code
        """
        if self.students:
            sort_list = list(self.students)
            sort_list.sort()
            return sort_list[0]
        return None

    def get_students(self):
        """
        获取班级所有学号
        :return: stu_code
        """
        return self.students


def q2_min_harvesters(original_list):
    """
    夏季割麦子， 需要用到大型收割机， 现在有 n 块麦地需要收割， 每个麦地的收割时间都不同，第n 个麦田的开始时 间是 start_n， 第 n 个麦田的结束时间是 end_n，下面是各个麦田收割的开始以及结束时间数组：[(1, 4), (3, 5), (0, 6),(5, 7), (3, 9)]， 其中(1,4)代表第一个麦田， 1 点开始， 4 点结束， 其他以此类推；
请通过编程计算出最少需要多少辆收割机能收完？ ps： 一个收割机在一个麦田上面继续收割时，必须连续工作直至当 前麦田收割完成；

    思路：
    1. 首先把输入的列数据按照起始时间升序排列 设为 original_list  结果：[(0, 6), (1, 4), (3, 5), (3, 9), (5, 7)]
    2. 把排序结果按起始和结束时间提取出来分为2个列表， 假设为 lst_start, lst_end
    3. 定义一个存储收割机条数的字典 dict_harvester, 数据格式形如 {1: [(0, 6), ...]}
    4. 取最小时间点和最大时间点, min_start, max_end
    5. 最小时间点和最大时间点循环，查找某个时段同时重叠最大个数
    :return:
    """
    # 1. 先排序
    original_list.sort(key=lambda x: x[0])  # 按起始时间降序

    # 2. 提取出起始时间和结束时间
    lst_start = [x[0] for x in original_list]
    lst_end = [x[1] for x in original_list]

    # 3. 定义收割机字典存储信息 来判断有多少条
    dict_harvester = {}

    # 4. 取最小时间点和最大时间点
    min_start = min(lst_start)
    max_end = max(lst_end)

    # 5. 循环查找最小时间点和最大时间点， 查找某个时段同时重叠最大个数
    for i in range(min_start, max_end + 1):
        # 此时起始和截止
        cur_start_end = (i, i + 1)

        # 临时列表，存储满足条件的数据
        lst_tmp_result = []

        # 查找覆盖此时段范围
        for idx, tmp_tuple in enumerate(original_list.copy(), 1):
            if tmp_tuple[0] <= cur_start_end[0] and tmp_tuple[1] >= cur_start_end[1]:
                # 满足条件，则从原本列表中删除
                original_list.remove(tmp_tuple)
                lst_tmp_result.append(tmp_tuple)

        if not dict_harvester:
            for idx, tmp_tuple in enumerate(lst_tmp_result, 1):
                dict_harvester[idx] = list(tmp_tuple)
        else:
            # 每项只比较一次，并更新最大值
            tmp_harvester = copy.deepcopy(dict_harvester)

            for idx, tmp_result in enumerate(lst_tmp_result, 1):
                for k, tmp_val in tmp_harvester.items():
                    # 只需判断结果中的起始时间大于存储的最大值
                    if tmp_result[0] >= tmp_val[1]:
                        # 如果满足，则更新
                        tmp_val[1] = tmp_result[0]
                        # 同时去掉这辆拖拉机
                        tmp_harvester.pop(k)
                        break
                    else:
                        # 不存在，则新增拖拉机
                        dict_harvester[len(tmp_harvester) + 1] = list(tmp_result)

    print(f'------ 至少需要的拖拉机个数： {len(dict_harvester)}')
    print(f'------ 拖拉机详情： {dict_harvester}')


def q3_min_difference(grid_data):
    """
    现在有一个围棋棋盘 （19*19），每个点上都记录有一个随机数值 （在 1 到 100 之间），我们在棋盘上面随机画一条
    直 线（只能横着画或者竖着画， 且不经过任何一个点），将棋盘分成 2 部分 A 和 B，A 和 B 棋盘上面的数值总和分别为
    SumA 和 SumB， 现在我们想找出这样一条直线画法， 使得 SumA 和 SumB 之间的差值最小， 给出此差值即可； 注意：
    不得使用 穷举法；

    思路：
    1. 由于画线只能横竖，我们要预先计算 每行和每列的棋格的数据，假设为 row_sums，col_sums
    2. 按行画线 遍历上下部分的总和差值，并记录，最小差值假设为 min_diff
    3. 按列画线，遍历左右部分的总和差值，与行线差值比较，若小则更新min_diff

    :param grid_data:
    :return:
    """
    # 计算每行和每列的总和
    row_sums = [sum(row) for row in grid_data]
    col_sums = [sum(col) for col in zip(*grid_data)]  # 列总和 转制

    # 总值，方便后面计算差值
    total = sum(row_sums)

    min_diff = float('inf')  # 最先差值，先设置为最大
    # 记录横 竖 方位，记录是几条线差值
    position_flag = 'row'
    line_num = 0

    # 遍历横向分割线
    for i in range(18):
        # 前i行求和
        sum_a = sum(row_sums[:i + 1])
        # 另一半
        sum_b = total - sum_a
        current_diff = abs(sum_a - sum_b)
        if current_diff < min_diff:
            min_diff = current_diff
            line_num = i

    # 遍历竖向分割线
    for j in range(18):
        # 前i行求和
        sum_a = sum(col_sums[:j + 1])
        # 另一半
        sum_b = total - sum_a
        current_diff = abs(sum_a - sum_b)
        if current_diff < min_diff:
            min_diff = current_diff
            # 置为竖线
            position_flag = 'col'
            line_num = j

    print(f'------ 最小差值： {min_diff}')
    print(f'------ 方向： {"横" if position_flag == "row" else "竖"}')
    print(f'------ 行数： {line_num + 1}')

    return min_diff


def q4_null():
    # 放弃
    print('------ 第四题放弃')


def q5():
    """
    请在上述 4 道题中，选择其中一题， 尝试用 ChatGPT 来解题， 比较 AI 代码和自己的代码的差异？说出其中的优缺 点，
    并给出如何借助 AI 提升开发效率的思路；

    思路：
    1. 选择第二题，使用deepseek来解题
    2. 差异点：
       2.1 代码风格：本人写的代码，比较传统，显示处理的一些逻辑； AI会使用新语法或者新特性，代码简洁
       2.2 思考逻辑：本人经验和知识储备关系限制，会尝试几种直白的方案； 看了AI的分析路径，他也会自己给自己提问，
       反问逻辑是否行的通，然后朝着最优解进行逐步分解， 高发散高容积思考
       2.3 算法复杂度：本人首先考量是完成任务再是调优，AI设计之处也会考虑
    3. 优缺点：
       AI优缺点：AI代码的简洁，空间复杂度低； 缺点：可能就是需要一定的知识储备
       自己写的优缺点：逻辑直观； 缺点：不够坚决，双重循环增加了时间复杂度
    4. AI提升开发效率的：
      1. 代码生成：基础的常见的算法可以让AI生成，人工代为审核判断
      2. 方案对比：把需求或方案交给AI思考，来和自己的方案进行对比，择优选择
      3. 异常信息解决：AI能快速反馈对应的解决方案
      4. 逻辑分析和优化：能提升整体的性能
    """

    # DeepSeek的输出
    def min_harvesters(intervals):
        # 提取开始和结束时间，并分别排序
        starts = sorted([x[0] for x in intervals])
        ends = sorted([x[1] for x in intervals])

        i = j = 0
        count = 0  # 当前正在工作的收割机数
        max_count = 0  # 记录历史最大值
        n = len(starts)

        # 双指针遍历开始和结束时间
        while i < n:
            if starts[i] < ends[j]:
                count += 1  # 新增一台收割机
                max_count = max(max_count, count)  # 更新最大值
                i += 1  # 处理下一个开始时间
            else:
                count -= 1  # 结束一台收割机的工作
                j += 1  # 处理下一个结束时间
        return max_count

    # 测试
    intervals = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9)]
    print(min_harvesters(intervals))  # 输出：4


def test_q1():
    """
    验证类
    :return:
    """
    init_data1 = [2025001, 2025002, 2025003, 2025004, 2025005]
    init_data2 = None  # 测试为空的情况

    student_code1 = Q1StudentCode(init_data1)
    student_code1.add(2025001)
    student_code1.add(2025006)
    student_code1.add(2025007)

    # 随机增加数据, 尽量可验证结果准确性
    start_code = 2024001
    end_code = 2026001
    size = 20
    for i in range(size):
        student_code1.add(random.randint(start_code, end_code))

    print(f'---- exixst: {student_code1.exists(2025001)}')  # 输出: True
    print(f'---- exixst: {student_code1.exists(2025008)}')  # 输出: False
    print(f'---- remove: {student_code1.remove(2025001)}')  # 输出: 2025001
    print(f'---- get_random: {student_code1.get_random()}')  # 随机输出一个学号

    student_code1.remove(2025001)  # 输出: True
    student_code1.remove(202500111)  # 输出: False
    print(f'---- get_students: {student_code1.get_students()}')  # 输出: 数据
    print(f'---- get_min: {student_code1.get_min()}')  # 输出: 2025002


def test_q2():
    """
    验证 试题2
    :return:
    """
    init_data = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9)]

    q2_min_harvesters(init_data)


def test_q3():
    """
    验证 试题3
    :return:
    """
    # 生成一个19x19的随机网格，每个元素在1到100之间
    grid_data = [[random.randint(1, 100) for _ in range(19)] for _ in range(19)]
    q3_min_difference(grid_data)


if __name__ == '__main__':
    # 验证题1
    print('------ 第一题 ------')
    test_q1()
    # 验证题2
    print('\n------ 第二题 ------')
    test_q2()
    # 验证题3
    print('\n------ 第三题 ------')
    test_q3()

    print('\n------ 第四题 ------')
    q4_null()

    print('\n------ 第四题 ------')
    print(q5.__doc__)
